package Prac;

import java.util.*;

public class P12_2 {

    //topk问题,确定比较的元素,确定"大小",取小用大,取大用小

    //找出数组中最小的k个数。以任意顺序返回这k个数均可
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        if(arr==null||k==0){
            return ret;
        }
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i : arr) {
            queue.offer(i);
            if(queue.size()>k){
                queue.poll();
            }
        }

        int i = 0;
        while (!queue.isEmpty()){
            ret[i++] = queue.poll();
        }
        return ret;
    }

    //给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
    class Freq{
        int val;
        int times;

        public Freq(int val, int times) {
            this.val = val;
            this.times = times;
        }
    }

    public int[] topKFrequent(int[] nums, int k) {
        int[] ret = new int[k];
        if(nums==null||k==0){
            return ret;
        }
        Queue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return o1.times-o2.times;
            }
        });

        Map<Integer,Integer> map = new HashMap<>();
        for (int i:nums) {
            if(map.containsKey(i)){//i这个元素已经出现
                int times = map.get(i);
                map.put(i,times+1);
            }else {
                map.put(i,1);//这个元素第一次出现
            }
        }
        for(Map.Entry<Integer,Integer> entry :map.entrySet()){
            if(queue.size()<k){
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
            }else {
                queue.offer(new Freq(entry.getKey(),entry.getValue()));
                queue.poll();
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll().val;
        }
        return ret;
    }
}
